1. Field of the Invention
The present invention is directed to compiling and interpreting computer programs. It particularly concerns synchronization between execution threads.
2. Background Information
FIG. 1 depicts a typical computer system 10. A microprocessor 11 receives data, and instructions for operating on them, from on-board cache memory or further cache memory 12, possibly through the mediation of a cache controller 13, which can in turn receive such data from system read/write memory (xe2x80x9cRAMxe2x80x9d) 14 through a RAM controller 15, or from various peripheral devices through a system bus 16.
The RAM 14""s data and instruction contents will ordinarily have been loaded from peripheral devices such as a system disk 17. Other sources include communications interface 18, which can receive instructions and data from other computer systems.
The instructions that the microprocessor executes are machine instructions. Those instructions are ultimately determined by a programmer, but it is a rare programmer who is familiar with the specific machine instructions in which his efforts eventually result. More typically, the programmer writes higher-level-language xe2x80x9csource codexe2x80x9d from which a computer software-configured to do so generates those machine instructions, or xe2x80x9cobject code.xe2x80x9d
FIG. 2 represents this sequence. FIG. 2""s block 20 represents a compiler process that a computer performs under the direction of compiler object code. That object code is typically stored on the system disk 17 or some other machine-readable medium, and it is loaded by transmission of electrical signals into RAM 15 to configure the computer system to act as a compiler. But the compiler object code""s persistent storage may instead be provided in a server system remote from the machine that performs the compiling. The electrical signals that carry the digital data by which the computer systems exchange the code are exemplary forms of carrier waves transporting the information.
The compiler converts source code into further object code, which it places in machine-readable storage such as RAM 15 or disk 17. A computer will follow that object code""s instructions in performing an application 21 that typically generates output from input. The compiler 20 is itself an application, one in which the input is source code and the output is object code, but the computer that executes the application 21 is not necessarily the same as the one that executes the compiler application.
The source code need not have been written by a human programmer directly. Integrated development environments often automate the source-code-writing process to the extent that for many applications very little of the source code is produced xe2x80x9cmanually.xe2x80x9d As will be explained below, moreover, the xe2x80x9csourcexe2x80x9d code being compiled may sometimes be low-level code, such as the byte-code input to the Java(trademark) virtual machine, that programmers almost never write directly. (Sun, the Sun Logo, Sun Microsystems, and Java are trademarks or registered trademarks of Sun Microsystems, Inc., in the United States and other countries.) And, although FIG. 2 may appear to suggest a batch process, in which all of an application""s object code is produced before any of it is executed, the same processor may both compile and execute the code, in which case the processor may execute its compiler application concurrently withxe2x80x94and, indeed, in a way that can be dependent uponxe2x80x94its execution of the compiler""s output object code.
So the sequence of operations by which source code results in machine-language instructions may be considerably more complicated than one may infer from FIG. 2. To give a sense of the complexity that can be involved, we discuss by reference to FIG. 3 an example of one way in which various levels of source code can result in the machine instructions that the processor executes. The human application programmer produces source code 22 written in a high-level language such as the Java programming language. In the case of the Java programming language, a compiler 23 converts that code into xe2x80x9cclass files.xe2x80x9d These predominantly include routines written in instructions, called xe2x80x9cbyte codesxe2x80x9d 24, for a xe2x80x9cvirtual machinexe2x80x9d that various processors can be programmed to emulate. This conversion into byte codes is almost always separated in time from those codes"" execution, so that aspect of the sequence is depicted as occurring in a xe2x80x9ccompile-time environmentxe2x80x9d 25 separate from a xe2x80x9crun-time environmentxe2x80x9d 26, in which execution occurs.
Most typically, the class files are run by a processor under control of a computer program known as a virtual machine 27, whose purpose is to emulate a machine from whose instruction set the byte codes are drawn. Much of the virtual machine""s action in executing these codes is most like what those skilled in the art refer to as xe2x80x9cinterpreting,xe2x80x9d and FIG. 3 shows that the virtual machine includes an xe2x80x9cinterpreterxe2x80x9d 28 for that purpose. The resultant instructions typically involve calls to a run-time system 29, which handles matters such as loading new class files as they are needed and performing xe2x80x9cgarbage collection,xe2x80x9d i.e., returning allocated memory to the system when it is no longer needed.
Many virtual-machine implementations also actually compile the byte codes concurrently with the resultant object code""s execution, so FIG. 3 depicts the virtual machine as additionally including a xe2x80x9cjust-in-timexe2x80x9d compiler 30. It may be that the resultant object code will make low-level calls to the run-time system, as the drawing indicates. In any event, the code""s execution will include calls to the local operating system 31.
It is not uncommon for a virtual-machine implementation both to compile and to interpret different parts of the same byte-code program. And, although the illustrated approach of first compiling the high-level code into byte codes is typical, the Java programming language is sometimes compiled directly into native machine code. So there is a wide range of mechanisms by which source codexe2x80x94whether high-level code or byte codexe2x80x94can result in the actual native machine instructions that the hardware processor executes. The teachings to be set forth below can be used in all of them, many of which, as was just explained, do not fit neatly into either the compiler or interpreter category. So we will adopt the term compiler/interpreter to refer to all such mechanisms, whether they be compilers, interpreters, hybrids thereof, or combinations of any or all of these.
In actual operation, the typical computer program does not have exclusive control over the machine whose operation it directs; a typical user concurrently runs a number of application programs. Of course, a computer that is not a multiprocessor machine can at any given instant be performing the instructions of only one program, but a typical multitasking approach employed by single-processor machines is for each concurrently running program to be interrupted from time to time to allow other programs to run, with the rate of such interruption being high enough that the programs"" executions appear simultaneous to the human user.
The task of scheduling different applications programs"" executions typically falls to the computer""s operating system. In this context, the different concurrently running programs are commonly referred to as different xe2x80x9cprocesses.xe2x80x9d In addition to scheduling, the operating system so operates the computer that the various processes"" physical code, data, and stack spaces do not overlap. So one process cannot ordinarily interfere with another. The only exceptions to this rule occur when a process specifically calls an operating-system routine (xe2x80x9cmakes a system callxe2x80x9d) intended for inter-process communication.
The operating system""s scheduling function can be used to divide processor time not only among independent processes but also among a single process""s different xe2x80x9cthreads of execution.xe2x80x9d Different execution threads are like different processes in that the operating system divides time among them so that they take can turns executing. They therefore have different call stacks, and the operating system has to swap out register contents when it switches between threads. But a given process""s different execution threads share the same data space, so they can have access to the same data without operating-system assistance. Indeed, they also share the same code space and can therefore execute the same instructions, although different threads are not in general at the same point in those instructions"" execution at the same time. By using threads to take advantage of the operating system""s scheduling function, the programmer can simplify the task of programming a plurality of concurrent operations; he does not have to write the code that explicitly schedules the threads"" concurrent executions.
FIG. 4 is a Java programming language listing of a way in which a programmer may code concurrent threads. The steps in that drawing""s fourth and fifth lines create new instances of the classes Transferor and Totaler and assign these objects to variables transferor and totaler, respectively. The Transferor and Totaler classes can be used to create new threads of control, because they extend the class Thread, as the nineteenth and twenty-ninth lines indicate. When a Thread object""s start( ) method is called, its run( ) method is executed in a new thread of control. So the sixth line""s transferor.start( ) statement results in execution of the method, defined in the twenty-second through twenty-seventh lines, that transfers an amount back and forth between two member variables, account_1 and account_2, of an object of the class Bank. And the seventh line""s totaler.start( ) statement results in execution of a method, defined in the thirty-second through thirty-fourth lines, that prints out the total of those member variables"" values. Note that neither method refers to the other; by taking advantage of the programming language""s thread facility, the programmer is relieved of the burden of scheduling.
There is not in general any defined timing between two concurrently running threads, and this is often the intended result: the various threads are intended to execute essentially independently of each other. But there are also many instances in which total independence would yield unintended results. For example, the b.transfer( ) method is intended to simulate internal transfers back and forth between two of a bank""s accounts, while the b.total( ) method is intended to print out the total of the bank""s account balances. Clearly, completely internal transfers should not change the bank""s account total. But consider what would happen if the transferor thread""s execution is interrupted between the fourteenth and fifteenth lines, i.e., between the time the amount is subtracted from one account and the time it is added to the other account. Intervening execution of the totaler thread could print the bank""s total out as a value different from the one that the simulation is intended to represent: the state of the simulated bank would be inconsistent.
To prevent such inconsistent results, mechanisms for inter-thread communication have been developed. In the example, the thirteenth and seventeenth lines include the xe2x80x9csynchronizedxe2x80x9d modifier. This directs the compiler/interpreter to synchronize its implementation of the transfer( ) and total( ) methods: before a thread begins execution of either method, it must obtain an exclusive xe2x80x9clockxe2x80x9d on the object on which the instance method is called. That means that no other thread can execute a synchronized method on that object until the first thread releases its lock. If a transferor thread is in the midst of executing b.transfer( ), for instance, it must have a lock on object b, and this means that the totaler thread will be blocked from executing b.total( ) until the transferor thread""s execution of transfer( ) has been completed.
Those familiar with the Java programming language will additionally recognize that a thread can lock an object even when it is not executing one of that object""s synchronized methods. FIG. 5 is a listing of source code for a class Bar containing two methods. The xe2x80x9csynchronizedxe2x80x9d statement in the onlyMe( ) method indicates that an execution thread must obtain a lock on the object f before it executes the subsequent code block, which calls the dosomething( ) method. FIG. 6 shows a possible result of compiling the onlyMe( ) method into Java-virtual-machine byte-code instructions. The fourth and eighth lines contain the mnemonics for the byte codes that direct the executing virtual machine respectively to acquire and release a lock on object f, which the topmost evaluation-stack entry references.
The particular way in which the compiler/interpreter obtains a lock on an object (also referred to as acquiring a xe2x80x9cmonitorxe2x80x9d associated with the object) depends on the particular compiler/interpreter implementation. (It is important at this point to recall that we are using the term compiler/interpreter in a broad sense to include, for instance, the functions performed by a Java virtual machine in executing the so-called byte code into which the Java programming language code is usually compiled; it is that process that implements monitor acquisition in response to the byte code whose mnemonic is monitorenter. Still, Java programming language code also is occasionally compiled directly into native machine code without the intervening step of byte-code generation. Indeed, monitor acquisition and release in the case of FIG. 4""s program would be performed without any explicit byte-code instruction for it, such as monitorexit, even if, as is normally the case, most of that code is compiled into byte code.)
The most natural way to implement a monitor is to employ available operating-system facilities for inter-thread and -process communication. Different operating systems provide different facilities for this purpose, but most of their applications-programming interfaces (xe2x80x9cAPIsxe2x80x9d) provide routines for operating on system data structures called xe2x80x9cmutexesxe2x80x9d (for xe2x80x9cmutual exclusionxe2x80x9d). A thread or process makes a system call by which it attempts to acquire a particular mutex that it and other threads and/or processes associate with a particular resource. The nature of mutex operations is such that an attempt to acquire a mutex is delayed (or xe2x80x9cblockedxe2x80x9d) if some other process or thread currently owns that particular mutex; when a mutex-acquisition attempt completes, the process or thread that performed the acquisition may safely assume that no other process or thread will complete an acquisition operation until the current process or thread releases ownership of the mutex. If all processes or threads that access a shared resource follow a convention of considering a particular shared mutex to xe2x80x9cprotectxe2x80x9d the resourcexe2x80x94i.e., if every process or thread accesses the resource only when it owns the mutexxe2x80x94then they will avoid accessing the resource concurrently.
The system-mutex approach has been employed for some time and has proven effective in a wide variety of applications. But it must be used judiciously if significant performance penalties or programming difficulties are to be avoided. Since the number of objects extant at a given time during a program""s execution can be impressively large, for instance, allocating a mutex to each object to keep track of its lock state would result in a significant run-time memory cost.
So workers in the field have attempted to minimize any such disincentives by adopting various monitor-implementation approaches that avoid storage penalties to as great an extent as possible. One approach is to avoid allocating any monitor space to an object until such time as a method or block synchronized on it is actually executed. When a thread needs to acquire a lock on an object under this approach, it employs a hash value for that object to look it up in a table containing pointers to monitor structures. If the object is already locked or currently has some other need for a monitor structure, the thread will find that monitor structure by consulting the table and performing the locking operation in accordance with that monitor structure""s contents. Otherwise, the thread allocates a monitor structure and lists it in the table. When synchronization activity on the object ends, the monitor structure""s space is returned to the system or a pool of monitor structures that can be used for other objects.
Since this approach allocates monitor structures only to objects that currently are the subject of synchronization operations, the storage penalty is minimal; although there are potentially very many extant objects at any given time, the number of objects that a given thread holds locked at one time is ordinarily minuscule in comparison, as is the number of concurrent threads. Unfortunately, although this approach essentially eliminates the excessive storage cost that making objects lockable could otherwise exact, it imposes a significant performance cost. Specifically, the time cost of the table lookup can be significant. It also presents scalability problems, since there can be contention for access to the table itself; the table itself must therefore be locked and thus can cause a bottleneck if the number of threads becomes large.
And the nature of object-oriented programming tends to result in extension of this performance cost to single-thread programming. There are classes of programming objects that are needed time and again in a wide variety of programming projects, and legions of programmers have duplicated effort in providing the same or only minimally different routines. One of the great attractions of object-oriented programming is that it lends itself to the development of class libraries. Rather than duplicate effort, a programmer can employ classes selected from a library of classes that are widely applicable and thoroughly tested.
But truly versatile class libraries need to be so written that each class is xe2x80x9cthread safe.xe2x80x9d That is, any of that class""s methods that could otherwise yield inconsistent results when methods of an object of that class are run in different threads will have to be synchronized. And unless the library provides separate classes for single-thread use, the performance penalty that synchronized methods exact will be visited not only upon multiple-thread programs but upon single-thread programs as well.
An approach that to a great extent avoids these problems is proposed by Bacon et al., xe2x80x9cThin Locks: Feather Weight Synchronization for Java,xe2x80x9d Proc. ACM SIGPLAN ""98, Conference on Programming Language Design and Implementation (PLDI), pp. 258-68, Montreal, June 1998. That approach is based on the recognition that most synchronization operations are locking or unlocking operations, and most such operations are uncontended, i.e., involve locks on objects that are not currently locked or are locked only by the same thread. (In the Java virtual machine, a given thread may obtain multiple simultaneous locks on the same object, and a count of those locks is ordinarily kept in order to determine when the thread no longer needs exclusive access to the object.) Given that these are the majority of the situations of which the monitor structure will be required to keep track, the Bacon et al. approach is to include in the object""s header a monitor structure that is only large enough (twenty-four bits) to support uncontended locking. That monitor includes a thread identifier, a lock count, and a xe2x80x9cmonitor shape bit,xe2x80x9d which indicates whether that field does indeed contain all of the monitor information currently required.
When a thread attempts to obtain a lock under the Bacon et al. approach, it first inspects the object""s header to determine whether the monitor-shape bit, lock count, and thread identifier are all zero and thereby indicate that the object is unlocked and subject to no other synchronization operation. If they are, as is usually the case, the thread places an index identifying itself in the thread-identifier field, and any other thread similarly inspecting that header will see that the object is already locked. It happens that in most systems this header inspection and conditional storage can be performed by a single atomic xe2x80x9ccompare-and-swapxe2x80x9d operation, so obtaining a lock on the object consists only of a single atomic operation if no lock already exists. If the monitor-shape bit is zero and the thread identifier is not zero but identifies the same thread as the one attempting to obtain the lock, then the thread simply retains the lock but performs the additional step of incrementing the lock count. Again, the lock-acquisition operation is quite simple. These two situations constitute the majority of locking operations.
But the small, twenty-four-bit header monitor structure does not have enough room for information concerning contended locking; there is no way to list the waiting threads so that they can be notified that the first thread has released the lock by writing zeroes into that header field. In the case of a contended lock, this forces the Bacon et al. arrangement to resort to xe2x80x9cspin locking,xe2x80x9d also known as xe2x80x9cbusy-waits.xe2x80x9d Specifically, a thread that attempts to lock an object on which some other thread already has a lock repeatedly performs the compare-and-swap operation on the object-header monitor structure until it finds that the previous lock has been released. This is obviously a prodigal use of processor cycles, but it is necessary so long as the monitor structure does not have enough space to keep track of waiting threads.
When the previously xe2x80x9cspinningxe2x80x9d thread finally does obtain access to the object, the Bacon et al. arrangement deals with the busy-wait problem by having that thread allocate a larger monitor structure to the object, placing an index to the larger structure in the header, and setting the object""s monitor-shape bit to indicate that it has done so, i.e., to indicate that the monitor information now resides outside the header. Although this does nothing to make up for the thread""s previous spinning, it is based on the assumption that the object is one for which further lock contention is likely, so the storage penalty is justified by the future spinning avoidance that the larger structure can afford.
A review of the Bacon et al. approach reveals that its performance is beneficial for the majority of synchronization operations, i.e., for uncontested or nested locks. But it still presents certain difficulties. In the first place, although the object-header-resident monitor structure is indeed relatively small in comparison with a fuller-featured monitors, it still consumes twenty-four bits in each and every object. Since this is three bytes out of an average object size of, say, forty bytes, that space cost is non-negligible. Additionally, the relatively small monitor size forces a compromise between monitor size and contention performance. As was mentioned above, initial contention results in the significant performance penalty that busy-waits represent. The Bacon et al. arrangement avoids such busy-waits for a given object after the first contention, but only at the expense of using the larger monitor structure, which needs to remain allocated to that object unless the previously contended-for object is again to be made vulnerable to busy-waits. In other words, the Bacon et al. arrangement keeps the object""s monitor structure xe2x80x9cinflatedxe2x80x9d because the object""s vulnerability to busy-waits would return if the monitor were xe2x80x9cdeflated.xe2x80x9d
Finally, the only types of synchronization operations with which the Bacon et al. approach can deal are the lock and unlock operations. It provides no facilities for managing other synchronization operations, such as those known as xe2x80x9cwait,xe2x80x9d xe2x80x9cnotify,xe2x80x9d and xe2x80x9cnotifyAllxe2x80x9d; it assumes the existence of heavy-weight monitor structures for those purposes.
An approach that addresses some of these shortcomings is the one described in commonly assigned U.S. patent application Ser. No. 09/245,778, which was filed on Feb. 5, 1999, by Agesen et al. for Busy-Wait-Free Synchronization and is hereby incorporated by reference. Compiler/interpreters that employ that approach allocate object structures in which the header includes a synchronization field, which can be as small as two bits, that can contain a code representing the object""s synchronization state. The codes may indicate, for instance, whether the object (1) is locked, (2) has threads waiting to lock it or be xe2x80x9cnotified onxe2x80x9d it, or (3) has no locks or waiters.
Since such a small field is not alone enough to contain all of the information concerning the object""s synchronization when various threads are synchronized on the object, synchronization operations employing the Agesen et al. approach will involve access to monitor structures temporarily assigned to the object to support those operations. A thread precedes access to such structures with an attempt to acquire what that application calls xe2x80x9cmeta-lockxe2x80x9d on the object, i.e., a lock on the monitor structures that contain the necessary synchronization information for that object. To acquire the meta-lock, the thread performs an atomic-swap operation, in which it atomically reads certain object-header fields"" contents and replaces them with values that identify the thread and the metalocked state. If the prior value did not already indicate that the object was meta-locked, then the thread concludes that it has access to the monitor structures. Otherwise, the thread places itself in line for the meta-lock acquisition.
A thread that has acquired the meta-lock makes whatever monitor-structure changes are necessary to the synchronization operation it is to perform, and it then releases the meta-lock by performing an atomic compare-and-swap operation, in which it replaces the previously read object-header contents if that header field""s contents are those that the thread left when it obtained the meta-lock. If the contents have changed, then the thread had one or more successors. In that situation, it does not change the object-header contents but instead communicates to a successor what the replacement contents would have been, and the successor acquires the meta-lock.
The Agesen et al. arrangement provides for efficient and versatile synchronization. But it requires expensive atomic operations both to acquire and to release metalocks.
I have found a way to obtain essentially the same advantages as Agesen et al. but without needing the expensive atomic compare-and-swap operation for meta-lock release. In accordance with my invention, an object""s monitor is inflated, as in the Agesen et al. and Bacon et al. approaches. And, as in the Agesen et al. approach, the header space required to support the monitor in absence of synchronization is very small. Indeed, it can be as small as single bit; my approach does not require xe2x80x9cmeta-locking,xe2x80x9d as the Agesen et al. approach does.
Specifically, a thread attempting to obtain a lock on an object consults a (potentially only one-bit) field in the object""s header that contains synchronization information, and this information indicates whether the object""s monitor has been inflated. If the monitor has not been inflated, the thread inflates the object""s monitor and locks the object. If the object""s monitor has already been inflated, and the monitor record into which the monitor has been inflated indicates that the object has been locked, then the thread attempting to obtain the lock increments a reference-count field in that monitor record to indicate that an additional thread is waiting to lock the object. It then repeats its reading of the synchronization information, typically after having had itself suspended and then having been awakened by another thread""s action in releasing that other thread""s lock on the object. It also reads the monitor record""s lock indicator if the object""s monitor is still inflated.
This process of re-checking the header synchronization information and the monitor record""s lock indicatorxe2x80x94and, typically, being suspended and subsequently awakenedxe2x80x94is repeated until either the object""s monitor is no longer inflated or its monitor record""s lock indicator no longer indicates that the object is locked. In the latter situation, the thread locks the object by making the lock indicator indicate that the object is again locked, whereas the thread recommences the lock operation in the former situation. Thus attempting to obtain a lock typically involves the expense of performing multiple machine operations together atomically, as will be explained below. In accordance with my invention, though, the operation of releasing the lock requires no such atomic operations. Specifically, a thread that is releasing a lock reads the reference count in the monitor record and changes the object""s synchronization information to indicate that the object""s monitor is not inflated if the reference count indicates that no other thread is waiting for the object. But the lock-releasing thread deflates the monitor by performing that synchronization-information change without atomically with that change confirming by reading the reference count that no further thread is waiting for a lock on the object. Now, another thread may have synchronized on the object between the time when the unlocking thread initially read the reference count and the time at which it deflated the object, in which case the unlocking thread has deflated the object""s monitor prematurely. An embodiment of the present invention will therefore check afterward to see whether the deflation it has performed was premature, and it will take steps to ensure that any other thread that has synchronized on that object in the interim recovers appropriately.
Although thus relying on a recovery operation may seem undesirable, because the recovery operation is relatively expensive, I have recognized that the overall expense of such a synchronization scheme is considerably less than that of one that employs atomic operations to avoid the need for a recovery scheme. This is because it is possible to make occurrences of such premature deflation extremely rare, so the cost on an average basis of occasionally performing a recovery operation is dwarfed by that of employing atomic operations to prevent the need for recovery.